`
https://leetcode.cn/problems/random-pick-with-blacklist/
`

class Solution {
  constructor(n, blacklist) {
    this.sz = n - blacklist.length;
    this.mapping = new Map();

    // 转化成集合，方便快速查询
    const blackSet = new Set(blacklist);

    let last = n - 1;
    for (let b of blacklist) {
      // 如果 b 已经在区间 [sz, N)，可以直接忽略
      if (b >= this.sz) {
        continue;
      }
      // 跳过所有黑名单中的数字
      while (blackSet.has(last)) {
        last--;
      }
      // 将黑名单中的索引映射到合法数字
      this.mapping.set(b, last);
      last--;
    }
  }

  pick() {
    // 随机选取一个索引
    const index = this._rand();

    // 这个索引命中了黑名单，需要被映射到其他位置
    if (this.mapping.has(index)) {
      return this.mapping.get(index);
    }

    // 若没命中黑名单，则直接返回
    return index;
  }

  _rand() {
    return Math.floor(Math.random() * this.sz)
  }
}

/** 
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(n, blacklist)
* var param_1 = obj.pick()
*/

// test
const solution = new Solution(7, [2, 3, 5]);
console.log(solution.pick()) // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
console.log(solution.pick()) // 返回 4
console.log(solution.pick()) // 返回 1
console.log(solution.pick()) // 返回 6
console.log(solution.pick()) // 返回 1
console.log(solution.pick()) // 返回 0
console.log(solution.pick()) // 返回 4